1. Field of the Invention
The present invention relates to an interleaving method and apparatus for providing parallel access in linear and interleaved order to a predetermined number of stored data samples, such as a turbo interleaver for a turbo decoder in mobile communication systems.
2. Description of the Related Art
Code concatenation is a practical technique for obtaining a code with a very long block length and a large error-correction capability. This is accomplished by combining two elementary codes. These codes have two distinct levels of encoding and decoding. The advantage of this coding scheme is that sequential decoding of the different codes can be performed. Thus, the decoding complexity of the overall code depends on the complexity of the decoder associated to each separate code used. This leads to a reduction of the decoding complexity.
The concept of turbo codes is an iterative decoding of two codes concatenated either in parallel or in serial using a Soft Input Soft Output (SISO) elementary decoder. Each elementary decoder therefore provides a decision and a likelihood ratio which quantifies the probability that the decision is correct. This information is passed to the next decoding stage in order to improve the bit error rate at each iteration. A turbo decoder can be implemented as certain number of pipelined identical elementary decoders depending on the number of iteration.
Turbo codes are able to achieve performances with a signal to noise ratio close to Shannon's theoretical limit, provided that the code is long enough and that a sufficiently large number of iterations is used in the iterative decoding process. Convolutional turbo codes are built using a parallel concatenation of two Recursive Systematic Convolutional (RSC) codes separated by a large random interleaver. The elementary decoder used in the iterative decoding process consists of two constituent SISO decoders, one for each RSC encoder, an interleaver and a deinterleaver. Further details are described for example in “Near Shannon limit error-correction coding: Turbo-Codes”, C. Berrou et al, in Proc. IEEE ICC'93, Geneva, Switzerland, pp. 1064–1070, May 1993, incorporated herein by reference.
In general, the interleaver randomizes an address of an input information or codeword and improves a distance property of the code word. It has been decided to use a turbo code in data transmission channels of third generation mobile communication systems, e.g. in a data channel of UMTS (Universal Mobile Telecommunications System) proposed by ETSI (European Telecommunication Standards Institute).
FIG. 1 shows a schematic block diagram of a conventional interleaver as for example disclosed in document WO 00/70771 for interleaving frame data. An address generator 150 generates a read address for changing the sequence of input data bits according to an input frame data size and an input clock CLK, and provides an interleaver memory 100 with the generated read address RA. The interleaver memory 100 sequentially stores input data DI in a write mode of operation, and outputs the stored data as output data DO according to the read address provided from the address generator 150 in a read mode of operation. A counter 130 counts the input clock and provides the clock count value to the interleaver memory 100 as a write address WA. Thus, the interleaver sequentially stores input data in the interleaver memory 100 in the write mode of operation, and outputs the data stored in the interleaver memory 100 according to the read address provided from the address generator 150 in the read mode of operation. Alternatively, it is also possible to change the sequence of the input data bits before storing them in the interleaver memory in the write mode of operation, and sequentially read the stored data in the read mode of operation.
If such an interleaver scheme is to be provided with a parallel access to the stored data in linear and interleaved order, multiport random access memory (RAMs) are used with K (K>1) reading ports. However, such multiport RAMs require large chip areas and are very expensive. Moreover, multiport RAMs with K reading ports may not be available from each ASIC (Application Specific Integrated Circuit) vendor, or the maximum number of available ports is at least limited at several vendors.